#include "LinkList.h"
#include <iostream>
#include <stddef.h>
#include "DynamicArray.h"

// 构造：初始化一个空链表，初始化大小为0，并创建一个头节点(初始化为0)
LinkList::LinkList() : size(0)
{
    head = new Node(0); // 构建头结点
}

LinkList::LinkList(const LinkList &list)
{
    size = list.size;
    head = new Node(0);
    Node *tp = head;                     // 初始指向新链表的头结点 tp 将用于构建新链表。
    Node *travelPoint = list.head->next; // 初始指向要复制的链表的第一个有效节点（即 head 后面的节点）
    while (travelPoint != nullptr)
    {
        // 双指针向前走，一个一个拷贝
        Node *newNode = new Node(travelPoint->value);
        tp->next = newNode;

        tp = tp->next;                   // 向前走
        travelPoint = travelPoint->next; // 向前走
    }
}

LinkList &LinkList::operator=(const LinkList &list)
{
    while (head != nullptr)
    {
        Node *nextNode = head->next; // 下一个节点存下来
        delete head;
        head = nextNode; // 接着指向下一个
    }
    size = list.size;
    head = new Node(0);
    Node *tp = head;
    Node *travelPoint = list.head->next;
    while (travelPoint != nullptr)
    {
        // 双指针向前走，一个一个拷贝
        Node *newNode = new Node(travelPoint->value);
        tp->next = newNode;
        tp = tp->next;
        travelPoint = travelPoint->next;
    }
    return *this;
}

LinkList::~LinkList()
{
    // 从第一个开始放
    while (head != nullptr)
    {
        Node *nextNode = head->next; // 不能直接释放head,否则会找不到下一个，所以需要将下一个节点存下来
        delete head;
        head = nextNode; // 接着指向下一个
    }
    // 该过程将持续，直到 head 指针为空（即所有节点都已被删除）
}

void LinkList::InsertTail(const ElementType &element) // O(n)
{
    Node *travelPoint = head;            // 遍历指针，代替head去遍历
    while (travelPoint->next != nullptr) // 还没有到尾部
    {
        travelPoint = travelPoint->next; // tP指向下一个节点
    }
    // Node *newNode = new Node(element); // 创建新节点
    // travelPoint->next = newNode;   // 放在尾部的下一个
    travelPoint->next = new Node(element);
    size++;
}

// 头插
void LinkList::InsertHead(const ElementType &element) // O(1)
{
    Node *newNode = new Node(element);
    newNode->next = head->next; // 先将其插入
    head->next = newNode;       // 接着重新指向
    size++;
}

// 根据位置插入
void LinkList::InsertByIndex(size_t index, const ElementType &element)
{
    if (index > size) // 不用等于size index可以取size 相当于尾插
    {
        std::cout << "位置非法！\n";
        return;
    }
    Node *travePoint = head; // 从头开始，到index结束，落到index - 1的位置  (对于index 最好不要减)
    for (size_t i = 0; i < index; i++)
    {
        travePoint = travePoint->next; // 落到index - 1的位置
    }
    Node *newNode = new Node(element);
    newNode->next = travePoint->next; // 指向原来的index位置
    travePoint->next = newNode;       //
    size++;
}

void LinkList::RemoveByIndex(size_t index) // O(n)  都是只动指针，不动元素本身
{
    if (index >= size)
    {
        std::cout << "删除位置非法!\n";
        return;
    }
    Node *travePoint = head;
    for (size_t i = 0; i < index; i++)
    {
        travePoint = travePoint->next; // 停在了index - 1 (不能停在index，否则回不了头操作不了)
    }
    Node *freeNode = travePoint->next; // freeNode 是index位置上
    travePoint->next = freeNode->next;
    delete freeNode;
    size--;
}

void LinkList::RemoveByElement(const ElementType &element) // O(n)
{
    Node *travePoint = head;
    while (travePoint->next != nullptr)
    {
        if (travePoint->next->value == element) // 有删的，原地不动
        {
            Node *freeNode = travePoint->next;
            travePoint->next = freeNode->next;
            delete freeNode;
            size--;
        }
        else
        {
            travePoint = travePoint->next;
        }
    }
}

ElementType *LinkList::FindByIndex(size_t index) // O(n)
{
    if (index >= size)
    {
        return nullptr;
    }
    Node *travePoint = head->next;
    for (size_t i = 0; i < index; i++)
    {
        travePoint = travePoint->next; // 停在了index
    }
    return &travePoint->value;
}

DARRAY::DynamicArray LinkList::FindByElement(const ElementType &element)
{
    DARRAY::DynamicArray array;
    Node *travePoint = head->next;
    while (travePoint != nullptr)
    {
        if (travePoint->value == element)
        {
            array.InsertTail(&travePoint->value);
        }
        travePoint = travePoint->next;
    }
    return array;
}

void LinkList::UpdateByIndex(size_t index, const ElementType &element)
{
    if (index >= size)
    {
        std::cout << "位置非法!\n";
        return;
    }
    Node *travePoint = head->next;
    for (size_t i = 0; i < index; i++)
    {
        travePoint = travePoint->next;
    }
    travePoint->value = element;
}

void LinkList::UpdateByElement(const ElementType &oldValue, const ElementType &newValue)
{
    Node *travePoint = head->next;
    while (travePoint != nullptr)
    {
        if (travePoint->value == oldValue)
        {
            travePoint->value = newValue;
        }
        travePoint = travePoint->next;
    }
}

void LinkList::BubbleSort()
{
    for (size_t i = 0; i < size - 1; i++)
    {
        Node *travePoint = head; // 每次循环都回到链表的开头
        for (size_t j = 0; j < size - i - 1; j++)
        {
            if (travePoint->next->value > travePoint->next->next->value)
            {
                Node *prev = travePoint->next;
                Node *back = prev->next;

                // 交换
                prev->next = back->next;
                back->next = prev;

                // 连接
                travePoint->next = back;
            }
            travePoint = travePoint->next;
        }
    }
}

void LinkList::Sort()
{
    FastSort(head->next, nullptr);
}

ElementType *LinkList::GetReserveIndex(size_t index)
{
    if (index > size || index == 0)
    {
        return nullptr;
    }
    Node *tavelPoint = head->next;
    for (size_t i = 0; i < size - index; i++)
    {
        tavelPoint = tavelPoint->next;
    }
    return &tavelPoint->value;
}

LinkList LinkList::Merge(const LinkList &list)
{
    LinkList result;
    Node *first = head->next;
    Node *sencond = list.head->next;
    while (first && sencond)
    {
        if (first->value < sencond->value)
        {
            result.InsertTail(first->value);
            first = first->next;
        }
        else
        {
            result.InsertTail(sencond->value);
            sencond = sencond->next;
        }
    }
    while (first)
    {
        result.InsertTail(first->value);
        first = first->next;
    }
    while (sencond)
    {
        result.InsertTail(sencond->value);
        sencond = sencond->next;
    }
    return result;
}

LinkList LinkList::FdIntrSctn(const LinkList &list)
{
    LinkList result;
    Node *first = head->next;
    Node *second = list.head->next;
    while (first && second)
    {
        if (first->value == second->value)
        {
            result.InsertTail(first->value);
            first = first->next;
            second = second->next;
        }
        else if (first->value < second->value)
            first = first->next;
        else if (first->value > second->value)
            second = second->next;
    }
    return result;
}

LinkList LinkList::FindUnionSet(const LinkList &list)
{
    LinkList result;
    Node *first = head->next;
    Node *second = list.head->next;
    while (first && second)
    {
        if (first->value == second->value)
        {
            result.InsertTail(first->value);
            first = first->next;
            second = second->next;
        }
        else if (first->value < second->value)
        {
            result.InsertTail(first->value);
            first = first->next;
        }
        else if (first->value > second->value)
        {
            result.InsertTail(second->value);
            second = second->next;
        }
    }
    while (first)
    {
        result.InsertTail(first->value);
        first = first->next;
    }
    while (second)
    {
        result.InsertTail(second->value);
        second = second->next;
    }
    return result;
}

LinkList LinkList::FindDifference(const LinkList &list)
{
    LinkList result;
    Node *first = head->next;
    Node *second = list.head->next;
    while (first && second)
    {
        if (first->value == second->value)
        {
            first = first->next;
            second = second->next;
        }
        else if (first->value < second->value)
        {
            result.InsertTail(first->value);
            first = first->next;
        }
        else if (first->value > second->value)
        {
            result.InsertTail(second->value);
            second = second->next;
        }
    }
    while (first)
    {
        result.InsertTail(first->value);
        first = first->next;
    }
    while (second)
    {
        result.InsertTail(second->value);
        second = second->next;
    }
    return result;
}

void LinkList::Reserve()
{
    Node *prev = nullptr;   //
    Node *cur = head->next; // 当前需要逆序的指针
    Node *Next = cur->next; //
    while (Next != nullptr)
    {
        cur->next = prev; // 逆序的关键
        prev = cur;       // p先动；
        cur = Next;       // c再动
        Next = cur->next; // N再动，N起到标记的作用，防止找不到后面的链表
    }
    cur->next = prev; // 最后一个节点单独逆序
    head->next = cur; // 新的head
}

void LinkList::Reserve2()
{
    head->next = reserve(head->next);
}

void LinkList::show()
{
    std::cout << "size: " << size << std::endl;
    Node *travelPoint = head->next; // 从头指针的下一个
    while (travelPoint != nullptr)  // 链表还未结束
    {
        std::cout << travelPoint->value << " ";
        travelPoint = travelPoint->next; // 遍历指针向后走
    }
    std::cout << std::endl;
}

void LinkList::FastSort(Node *start, Node *end) // 右区间是开区间
{
    // 终止条件
    if (start == end)
        return;
    Node *temp = start;       // 基准值指针
    Node *slow = start;       // 慢指针
    Node *fast = start->next; // 快指针
    while (fast != end)       // 快指针没有到结尾
    {
        // 快指针指向的值比基准值小
        if (fast->value < temp->value)
        {
            slow = slow->next;
            std::swap(slow->value, fast->value); // 交换快慢指针的值
        }
        fast = fast->next;
    }
    std::swap(temp->value, slow->value); // 将基准值归位
    FastSort(start, slow);               // [start,slow)
    FastSort(slow->next, end);
}

LinkList::Node *LinkList::reserve(Node *node)
{
    // 返回值是原来的尾巴，新链表的头
    if (node->next == nullptr) // 这个节点是尾巴 逆序完的头
        return node;
    else
    {
        Node *newHead = reserve(node->next); // 递归往后走，目的是找头，从后往前逆，否则会找不到后面的，不是像上一个逆序
        // 逆序核心
        node->next->next = node; // 链表1 2 3 4 5 将5指向4
        node->next = nullptr;    // 新尾巴 原来的头 指针指向空   (只对最后一个结点有效)
        return newHead;          // 返回新的头
    }
}

